{VERSION 6 0 "IBM INTEL NT" "6.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 
0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 
2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 
11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 
0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 12 1 {CSTYLE "" -1 
-1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 
0 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 
1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Author" 0 
19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 
8 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 90 "Proof of the existence of
 a bijection between Pi-Shapes of size 2n+2 and Motzkin of size n" }}
{PARA 19 "" 0 "" {TEXT -1 36 "Andy Lorenz, Yann Ponty, Peter Clote" }}
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 44 "Starting from the grammar for the
 pi-shapes:" }}{PARA 0 "" 0 "" {TEXT -1 46 "  S -> [T]S | epsilon\n  T
 -> [T][T]S | epsilon" }}{PARA 0 "" 0 "" {TEXT -1 103 "The system tran
slate into a system of equations on the generating functions, thanks t
o the DSV method: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "Sys1:
=\{S=z^2*S*T+1,T=z^4*S*T^2+1\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%
Sys1G<$/%\"SG,&*()%\"zG\"\"#\"\"\"F'F-%\"TGF-F-F-F-/F.,&*()F+\"\"%F-F'
F-)F.F,F-F-F-F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "Sol1:=al
lvalues(solve(Sys1,\{S,T\}));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%So
l1G6$<$/%\"TG,$**\"\"#!\"\",(\"\"\"F.*$)%\"zGF+F.F.*$,(F.F.*&F+F.F0F.F
,*&\"\"$F.)F1\"\"%F.F,#F.F+F.F.F1!\"#,&F.F.F/F.F,F./%\"SG*(,***F+F,F-F
.F1F:F;F,F.*(F+F,F-F.F;F,F.F.F,F/F,F.F1F:,(F.F,**F+F,F-F.F1F:F;F,F.*(F
+F,F-F.F;F,F.F,<$/F(,$**F+F,,(F.F.F/F.F2F,F.F1F:F;F,F./F=*(,***F+F,FIF
.F1F:F;F,F.*(F+F,FIF.F;F,F.F.F,F/F,F.F1F:,(F.F,**F+F,FIF.F1F:F;F,F.*(F
+F,FIF.F;F,F.F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "Now we choose \+
the solution for S(z) having positive coefficients, thus:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "Res1 := simplify(rhs(Sol1[2][2]));
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%Res1G*(%\"zG!\"#,**&\"\"#\"\"\"
)F&\"\"%F+F+*$)F&F*F+F+F+!\"\"*$,(F+F+*&F*F+F/F+F0*&\"\"$F+F,F+F0#F+F*
F+F+,(F.F+F+F0F1F+F0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "ser
ies(simplify(Res1),z,35);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#+C%\"zG\"
\"\"\"\"!F%\"\"#F%\"\"%F'\"\"'F(\"\")\"\"*\"#5\"#@\"#7\"#^\"#9\"$F\"\"
#;\"$B$\"#=\"$N)\"#?\"%)=#\"#A\"%)z&\"#C\"&6b\"\"#E\"&N=%\"#G-%\"OG6#F
%\"#I" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 44 "Starting from the gramma
r for the pi-shapes:" }}{PARA 0 "" 0 "" {TEXT -1 91 "  M -> [M]M | .M \+
| epsilon\nThe system translate into a system of equations, that we so
lve: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "Sys2:=\{M=z^2*M^2+
z*M+1\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%Sys2G<#/%\"MG,(*&)%\"zG
\"\"#\"\"\")F'F,F-F-*&F+F-F'F-F-F-F-" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 22 "Sol2:=solve(Sys2,\{M\});" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%%Sol2G6$<#/%\"MG,$*(\"\"#!\"\",(%\"zG\"\"\"F/F,*$,(*&
\"\"$F/)F.F+F/F,*&F+F/F.F/F,F/F/#F/F+F,F/F.!\"#F,<#/F(,$*(F+F,,(F.F/F/
F,F0F/F/F.F7F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "Once again, we \+
pick the solution whose coefficients are positive in a taylor expansio
n around z=0 " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "Res2 := rh
s(Sol2[2][1]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%Res2G,$*(\"\"#!\"
\",(%\"zG\"\"\"F+F(*$,(*&\"\"$F+)F*F'F+F(*&F'F+F*F+F(F+F+#F+F'F+F+F*!
\"#F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "series(simplify(Re
s2),z,35);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#+ao%\"zG\"\"\"\"\"!F%F%
\"\"#F'\"\"%\"\"$\"\"*F(\"#@\"\"&\"#^\"\"'\"$F\"\"\"(\"$B$\"\")\"$N)F*
\"%)=#\"#5\"%)z&\"#6\"&6b\"\"#7\"&N=%\"#8\"'MO6\"#9\"'s0J\"#:\"'nM&)\"
#;\"(znN#\"#<\"(#QOl\"#=\")%G*>=\"#>\")>?&3&\"#?\"*fvaU\"F+\"*BKw+%\"#
A\"+:/wH6\"#B\"+(zFF>$\"#C\"+,DSV!*\"#D\",w%=)pc#\"#E\",-Gx2I(\"#F\"-4
#yK-3#\"#G\"-H[yUPf\"#H\".67Z&Q(p\"\"#I\".\"Rw;wf[\"#J\"/2nMpN$R\"\"#K
-%\"OG6#F%\"#L" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 191 "The resulting \+
generating functions, although having very different expressions, turn
 out to be equivalent upon substitution of z with z^2 in that of Motzk
in followed by a z^2 multiplication. " }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 38 "simplify(Res1-1-z^2*subs(z=z^2,Res2));" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 136 "T
hus the n-th coefficients of the generating function for the Motzkin w
ords is equal to the 2n+2-th coefficient of that of the pi-shapes" }}}
}{MARK "0 0 0" 27 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 
2 33 1 1 }